/**
 * @Author ZhangCuirong
 * @Date 2025/9/12 11:08
 * @description:
 */
public class FindMaxInMountainArray {
    // 方法1：二分查找（高效，O(log n)）
    public static int findMax(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }

        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // 如果中间元素小于下一个元素，说明最大值在右侧
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            }
            // 否则最大值在左侧（包括当前mid）
            else {
                right = mid;
            }
        }

        // 循环结束时left == right，即为最大值位置
        return arr[left];
    }

    // 方法2：线性扫描（简单，O(n)）
    public static int findMaxLinear(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }

        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        // 测试用例
        int[] test1 = {1, 3, 5, 7, 6, 4, 2};
        int[] test2 = {10, 20, 30, 40, 50}; // 严格递增（可视为递减部分长度为0）
        int[] test3 = {50, 40, 30, 20, 10}; // 严格递减（可视为递增部分长度为0）
        int[] test4 = {1, 2, 3, 2, 1};
        int[] test5 = {5}; // 单元素数组

        System.out.println(findMax(test1)); // 输出：7
        System.out.println(findMax(test2)); // 输出：50
        System.out.println(findMax(test3)); // 输出：50
        System.out.println(findMax(test4)); // 输出：3
        System.out.println(findMax(test5)); // 输出：5
    }
}
